// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 如果输入切片可以划分为两个总和相等的子集，则返回 true，否则返回 false
func canPartition(array []int) bool {
	// 计算输入切片的长度
	n := len(array)

	// 计算输入切片中所有元素的总和
	sum := 0
	for _, num := range array {
		sum += num
	}

	//如果和为奇数，则无法将输入切片分成两个和相等的子集，因此返回 false
	if sum%2 != 0 {
		return false
	}

	//计算每个子集的目标总和，即总和的一半
	target := sum / 2

	//初始化一个长度为 target+1 的布尔切片，并将第一个元素设置为 true
	dp := make([]bool, target+1)
	dp[0] = true

	//迭代输入切片，对于每个元素，以相反的顺序迭代布尔切片，
	//如果 dp[j] 或 dp[j-array[i]] 为真，则将每个元素 dp[j] 更新为真，
	for i := 0; i < n; i++ {
		for j := target; j >= array[i]; j-- {
			dp[j] = dp[j] || dp[j-array[i]]
		}
	}

	//返回布尔切片的最后一个元素，表示是否可以创建总和等于目标的子集
	return dp[target]
}

func main() {
	//定义示例输入切片
	array := []int{1, 5, 11, 5}

	//调用 canPartition() 函数并打印其结果
	fmt.Println(canPartition(array))
}

//$ go run interview12-4.go
//true
